'''
Author: your name
Date: 2021-12-12 14:34:38
LastEditTime: 2021-12-12 14:38:47
LastEditors: Please set LastEditors
Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
FilePath: /DAA/Chain_Matrix_Multiplication/CMM.py
'''

def matrixChain(p):
    num = len(p) - 1
    m = [[0] * num for _ in range(num)]
    s = [[0] * num for _ in range(num)]
    for d in range(1, num):
        for i in range(1, num - d + 1):
            j = i + d
            m[i - 1][j - 1] = 9999999999
            for k in range(i, j):
                template = m[i - 1][k - 1] + m[k][ - 1] + p[i - 1]*p[k]*p[j]
                if template < m[i -1][j - 1]:
                    m[i - 1][j - 1] = template
                    s[i - 1][j - 1] = k
    return m, s

def getFun(s, i, j):
    if i == j:
        print("A" + str(i), end="")
    else:
        print("(", end="")
        getFun(s, i, int(s[i - 1][j - 1]))
        getFun(s, int(s[i - 1][j -1]) + 1, j)
        print(")", end="")
        
